package com.cuz.hot100;

import java.util.*;

public class Q40combinedSum2 {

    public static void main(String[] args) {
        //输入：candidates = [2,3,6,7], target = 7
        //输出：[[2,2,3],[7]]
        //[10,1,2,7,6,1,5]
        //8
        //输出：
        //[[1,2,5],[1,7],[2,6]]
        //预期结果：
        //[[1,1,6],[1,2,5],[1,7],[2,6]]
        //[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
        //30
//        int[] arr = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        //[2,5,2,1,2]
        //5
        int[] arr = {10, 1, 2, 7, 6, 1, 5};
        System.out.println(combinationSum3(arr, 8));
    }

    public static List<List<Integer>> combinationSum3(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) {
            return Collections.emptyList();
        }
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        process(candidates, 0, 0, target, new LinkedList<>(), res);
        return res;

    }

    private static void process(int[] candidates, int startIndex, int curSum, int target, LinkedList<Integer> tempRes, List<List<Integer>> res) {
        if (curSum == target) {
            res.add(new ArrayList<>(tempRes));
        }
        if (curSum > target) {
            return;
        }
        int tempIndex=startIndex;
        for (; tempIndex < candidates.length; tempIndex++) {
            if (tempIndex > startIndex && candidates[tempIndex] == candidates[tempIndex - 1]) {
                continue;
            }
            if (candidates[tempIndex] + curSum <= target) {
                tempRes.addLast(candidates[tempIndex]);
                process(candidates, tempIndex + 1, curSum + candidates[tempIndex], target, tempRes, res);
                tempRes.removeLast();
            }
        }
    }


}
